Secret sharing schemes are known as a cryptographic technology that can divide secret information into a plurality of items of shared information (shares) and then reconstruct the secret only when a predetermined number of shares have been gathered.
Because each individual share (item of shared information) is information having no correlation with the secret information, managing this shared information by sharing it among a plurality of sites can prevent a cheater who has dishonestly acquired shared information from reconstructing the original secret information. As a result, a secret-sharing scheme can maintain high security against disclosure of secrets.
In addition, even in the event of the loss of a number of items of shared information, a secret-sharing scheme enables the restoration of secret information as long as a predetermined number of items of shared information remain, and therefore can maintain high security against information loss.
The best-known scheme among such secret-sharing schemes is the (k, n) threshold secret-sharing scheme described in Non-Patent Document 1. Among secret-sharing schemes, this scheme is characterized by: (1) the division of secret information into n items of shared information, (2) the ability to restore the secret information when any k shares among these shares are collected, and (3) the inability to obtain any information relating to the secret from partial information of less than k shares.
The (k, n) threshold secret-sharing scheme described in Non-Patent Document 1 does not take into consideration the dishonesty of the person managing the shared information or the malfunctioning of a device that manages the shared information. As a result, when k items of shared information are collected to reconstruct a secret, the occurrence of even one item of shared information that differs from the original information not only prevents the correct reconstruction of the secret information but also prevents the detection of the fact that the reconstructed secret information differs from the original secret information.
In order to solve this problem, a method is employed in the secret-sharing scheme described in Non-Patent Document 2 or Non-Patent Document 3 that can detect difference of the reconstructed secret information from the original secret information at the time of reconstructing a secret, even when k−1 items of falsified shared information have been collected.
Schemes that can not only detect that falsification has occurred at the time of reconstruction, but that can also identify which shared information was falsified are described in Non-Patent Documents 4-6.
According to the secret-sharing scheme described in Non-Patent Document 4, there is a high probability that all t items of falsified shared information can be identified if the number t of items of falsified shared information is within the range k≧2t+1.
Non-Patent Document 5 and Non-Patent Document 6 describe secret-sharing schemes in which there is a high probability that all falsified shared information can be identified if the number of cheaters t is within the range of k≧3t+1, although the number of items of falsified shared information that can be identified is less than that of the method described in Non-Patent Document 4.
When attempting to enable identification of a multiplicity of items of falsified shared information in the secret-sharing schemes such as described in Non-Patent Documents 4-6, the data size of the items of shared information increases proportionately. On the other hand, when attempting to decrease the data size of each item of shared information, the number of items of falsified shared information that can be identified decreases.
In the former example, the secret-sharing schemes described in Non-Patent Documents 5 and 6 have the disadvantage of not being able to identify falsified shared information if the number t of items of falsified shared information is not within the range that satisfies k≧2t+1, which is narrower than the case of Non-Patent Document 4, but has the advantage of enabling a greater decrease of the data size of each item of shared information than the secret-sharing scheme described in Non-Patent Document 4.
Specifically, the data size of a share is p*q^(3n−3) in the method of Non-Patent Document 4. In contrast, the size of a share is p*q^(t+1) in the method of, for example, Patent Document 5, which is relatively small. Here, p is order of a predetermined finite field and is a power of a prime number, and q is a prime number that satisfies:q≧n*p 